package com.zwj.interview.DFS;



/**
 * @Author: Zwj
 * @Date: 2022/9/15 11:49
 * 力扣543
 */
public class 树的直径 {

    //所谓二叉树的直径，就是左右子树的最大深度之和，那么直接的想法是对每个节点计算左右子树的最大高度，
    // 得出每个节点的直径，从而得出最大的那个直径。


    /**
     * 一棵树的最大直径有两种可能：
     * 1：经过根节点
     * 经过根节点的话，那么根节点+max(左子树的高度)+max(右子树的高度）
     * 2：不经过根节点
     * 那么就是左右子树中最大的距离，max(左子树距离，右子树距离)
     */



    public int diameterOfBinaryTree(TreeNode root) {
      return process(root).maxInstance;
    }


   public static  class Info{
        public int maxInstance;
        public int height;

        public Info(int instance,int h){
            maxInstance=instance;
            height=h;
        }
   }


   //对于任何一个节点，需要返回两部分东西
   public  static Info process(TreeNode root){
          if(root==null){
              new Info(0,0);
          }
          Info left=process(root.left);
          Info right=process(root.right);

          int height=1+Math.max(left.height, right.height);
          //不经过根节点
          int p1=Math.max(left.maxInstance,right.maxInstance);
           //经过根节点
          int p2=left.height+right.height+1;
          //最终距离就是两种情况的最大值
          int maxDistance=Math.max(p1,p2);
          return new Info(maxDistance,height);

   }

}